P3469 BLO-Blockade

这道题一看就是到好（shui）题，毕竟自己因long long的问题的错了几次。好吧，不废话，开始讲解：

这道题一看就是求无向图中，去掉一个点后无法连通的点对，但注意：

1. $( x , y )$ 和 $( y , x )$ 算作不同的点对
2. 即使点被删除后，也要计入无法连通数，但显然他们是不联通的

首先 $i$ 跟其他$n-1$个点肯定不能互通。如果$i$是割点，那么去掉$i$之后的几个不同连通分量就不能互通,那我们现在就想办法求一下去掉$i$后被切断的连通分量。先观察一下下图：

黄点是一个割点，我们先考虑以它为根的子树的联通情况：

我们用$child[u]$表示以$u$为根的子树的大小，显然

$child[u]=\sum_{v \in u}child[v]$

这个我们可以在$Tarjan$中算出。

我们再定义$sum$为当前u已经遍历到的子树的节点个数，$s$为去掉$u$点后子树中的点无法连通的情况。

那么，每次遍历子节点$v$ , $s=s+sum*child[v]$ , $sum=sum+child[v]$

现在在考虑子树内部与外部的联通情况，$u$的子树大小为$sum$,外部节点为$n-sum-1$,去掉点$u$后，这些点也是无法连通的，$t$为去掉u点后子树中的点与外部的点无法连通的情况。

那么，$t=sum*(n-sum-1)$

结合注意事项1,2，我们可以得到：$Ans[u]=[s+t+(n-1)]*2$，这就是最后的答案了。

代码如下：

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 100000;
int n,m,x,y;
vector< int > Graph[ MAXN + 5 ];

void Read( int &x ) {
	int f = 1;
	x = 0;
	char s = getchar( );
	
	while( s < '0' || s > '9' ) {
		if( s == '-' ) f = -1;
		s = getchar( );
	}
	while( s >= '0' && s <= '9' ) {
		x = x * 10 + s - 48;
		s = getchar( );
	}
	x *= f;
}
void Write( long long x ) {
	if( x < 0 ) {
		x = -x;
		putchar('-');
	}
	if( x >= 10 ) Write( x / 10 );
	putchar( x % 10 + 48 );
}
int Max( int x , int y ) {
	return x > y ? x : y;
}
int Min( int x , int y ) {
	return x < y ? x : y;
}

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , child[ MAXN + 5 ] , depth;
long long Ans[ MAXN + 5 ];

void Tarjan( int u , int fa ) {
	dfn[ u ] = low[ u ] = ++ depth;
	child[ u ] = 1;
	//printf("%d %d\n",u,depth);
	long long sum = 0;
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( v == fa ) continue;
		
		if( !dfn[ v ] ) {
			Tarjan( v , u );
			child[ u ] += child[ v ];
			
			if( low[ v ] >= dfn[ u ] ) {
				Ans[ u ] += child[ v ] * sum;
				sum += child[ v ];
			}
			low[ u ] = Min( low[ u ] , low[ v ] );
		}
		
		else if( v != fa && dfn[ u ] > dfn[ v ] )
			low[ u ] = Min( low[ u ] , dfn[ v ] );
	}
	Ans[ u ] = ( Ans[ u ] + sum * ( n - sum - 1 ) + n - 1 ) * 2;
}

int main( ) {
	Read( n ) , Read( m );
	for( int i = 1 ; i <= m ; i ++ ) {
		Read( x ) , Read( y );
		Graph[ x ].push_back( y );
		Graph[ y ].push_back( x );
	}
	Tarjan( 1 , -1 );
	
	for( int i = 1 ; i <= n ; i ++ )
		Write( Ans[ i ] ) , putchar('\n');
	return 0;
}